Міністерство освіти та науки України Національний університет “Львівська політехніка” Кафедра ПЗ КУРСОВА РОБОТА з курсу: “Методи та засоби комп’ютерних інформаційних технологій” СТИСНЕННЯ ІНФОРМАЦІЇ МЕТОДОМ ХАФФМАНА Виконав: Ст.гр. КН-3 Прийняв: Львів 2009 р. ЗМІСТ  TOC \o "1-3" \h \z \u  HYPERLINK \l "_Toc217749147" ЗМІСТ  PAGEREF _Toc217749147 \h 2  HYPERLINK \l "_Toc217749148" ВСТУП  PAGEREF _Toc217749148 \h 2  HYPERLINK \l "_Toc217749149" ПОСТАНОВКА ЗАВДАННЯ  PAGEREF _Toc217749149 \h 3  HYPERLINK \l "_Toc217749150" 1. АНАЛІТИЧНИЙ РОЗДІЛ  PAGEREF _Toc217749150 \h 3  HYPERLINK \l "_Toc217749151" 1.1 Способи стиснення інформації  PAGEREF _Toc217749151 \h 3  HYPERLINK \l "_Toc217749152" 1.2. Алгоритм RLE  PAGEREF _Toc217749152 \h 4  HYPERLINK \l "_Toc217749153" 1.3. Алгоритм KWE  PAGEREF _Toc217749153 \h 5  HYPERLINK \l "_Toc217749154" 1.4. Алгоритм Хаффмана  PAGEREF _Toc217749154 \h 6  HYPERLINK \l "_Toc217749155" 2. ІСНУЮЧІ АНАЛОГИ  PAGEREF _Toc217749155 \h 8  HYPERLINK \l "_Toc217749156" 2.1 WinRar  PAGEREF _Toc217749156 \h 8  HYPERLINK \l "_Toc217749157" 2.2 WinZip  PAGEREF _Toc217749157 \h 10  HYPERLINK \l "_Toc217749158" 3.ПРОЕКТНИЙ РОЗДІЛ  PAGEREF _Toc217749158 \h 12  HYPERLINK \l "_Toc217749159" 3.1. Структури даних для методу Хаффмана  PAGEREF _Toc217749159 \h 12  HYPERLINK \l "_Toc217749160" 3.2. Швидший алгоритм побудови дерева  PAGEREF _Toc217749160 \h 13  HYPERLINK \l "_Toc217749161" 3.3. Алгоритм обчислення кодів Хаффмана  PAGEREF _Toc217749161 \h 13  HYPERLINK \l "_Toc217749162" 3.4. Розмір і формат запису упакованих даних  PAGEREF _Toc217749162 \h 14  HYPERLINK \l "_Toc217749163" 3.5. Кодування даних  PAGEREF _Toc217749163 \h 15  HYPERLINK \l "_Toc217749164" 3.6. Декодування даних  PAGEREF _Toc217749164 \h 16  HYPERLINK \l "_Toc217749165" 4. ІНТЕРФЕЙС ПРОГРАМИ  PAGEREF _Toc217749165 \h 17  HYPERLINK \l "_Toc217749166" 5. ТЕКСТ ПРОГРАМИ  PAGEREF _Toc217749166 \h 18  HYPERLINK \l "_Toc217749167" 6. ЕКСПЕРИМЕНТАЛЬНИЙ РОЗДІЛ  PAGEREF _Toc217749167 \h 30  HYPERLINK \l "_Toc217749168" Таблиця порівняння стиску файлів різних форматів  PAGEREF _Toc217749168 \h 31  HYPERLINK \l "_Toc217749169" ВИСНОВОК  PAGEREF _Toc217749169 \h 31  HYPERLINK \l "_Toc217749170" Використана література  PAGEREF _Toc217749170 \h 33  ВСТУП Характерною особливістю більшості типів даних є їх надлишковість. Ступінь надлишковості даних залежить від типу даних. Наприклад, для відеоданих ступінь надлишковості в декілька разів більша ніж для графічних даних, а ступінь надлишковості графічних даних, у свою чергу, більша за ступінь надлишковості текстових даних. Іншим фактором, що впливає на ступінь надлишковості є прийнята система кодування. Прикладом систем кодування можуть бути звичайні мови спілкування, які є ні чим іншим, як системами кодування понять та ідей для висловлення думок. Так, встановлено, що кодування текстових даних за допомогою засобів української мови дає в середньому надлишковість на 20-25% більшу ніж кодування аналогічних даних засобами англійської мови. Для людини надлишковість даних часто пов'язана з якістю інформації, оскільки надлишковість, як правило, покращує зрозумілість та сприйняття інформації. Однак, коли мова йде про зберігання та передачу інформації засобами комп'ютерної техніки, то надлишковість відіграє негативну роль, оскільки вона приводить до зростання вартості зберігання та передачі інформації. Особливо актуальною є ця проблема у випадку необхідності обробки величезних обсягів інформації при незначних об'ємах носіїв даних. У зв'язку з цим постійно виникає проблема позбавлення надлишковості або стиснення даних. Коли методи стиснення даних застосовуються до готових файлів, то часто замість терміну "стиснення даних" вживают...